package week06

import "fmt"

// 递归函数中加法运算的次数
var count int = 0

/*
功能: 判断计算 Fib(x)时进行了几次加法运行
*/
func Question1(x int) int {

	Fib(x)
	fmt.Println("count=", count)
	return count
}

func Fib(x int) int {
	if x == 0 || x == 1 {
		return x
	}
	count++
	return Fib(x-1) + Fib(x-2)
}

// 跟具体矩阵法逻辑无关, 考察代码阅读能力
func Question2(n int) int {
	// 奇数计算2次，偶数算1次
	// 44 22 11 5 2 1  = 6 + 2(奇数个数)
	i := 0
	for n > 0 {
		if n > 2 && n%2 == 1 {
			i++ // 奇数额外算一个矩阵
		}
		n /= 2
		i++ // coef_matrix *= coef_matrix
	}

	fmt.Printf("%d次矩阵相乘运算\n", i)
	return i
}

var GridDefault [][]int = [][]int{
	{1, 3, 7, 1, 4},
	{2, 2, 4, 6, 1},
	{5, 3, 1, 8, 1},
	{6, 2, 3, 2, 5},
	{2, 1, 4, 1, 3},
}

/*
功能: 求从左上角grid[0,0]到右下角grid[m-1,n-1]距离之和最短的路径
*/
func Question4(grid [][]int) int {
	m, n := len(grid), len(grid[0]) // input grid[m,n]

	var dist [][]int

	row := 0
	for ; row < m; row++ {
		arr := make([]int, n) // dist由长度为n的arr 一层一层的组合

		// 处理每列的第一个数
		if row == 0 {
			arr[0] = grid[0][0]
		} else {
			arr[0] = dist[row-1][0] + grid[row][0]
		}

		for i := 1; i < n; i++ {
			if row == 0 {
				arr[i] = arr[i-1] + grid[row][i] //第一行不用min
			} else {
				arr[i] = min(dist[row-1][i], arr[i-1]) + grid[row][i]
			}
		}

		dist = append(dist, arr)
	}

	for row = 0; row < m; row++ {
		for j := 0; j < n; j++ {
			fmt.Printf("%3d ", dist[row][j])
		}
		fmt.Println()
	}

	return dist[m-1][n-1]
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}
